反转单链表【Java数据结构】精讲 | 您所在的位置:网站首页 › 反转单链表 java › 反转单链表【Java数据结构】精讲 |
题目:给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。 思路:反转单链表, 即原来的首节点变成尾节点,尾节点变成首节点,所以我们首先要将首节点的next指向null,此时要注意,如果我们没有对首节点的原指向进行存储操作的话,就会丢失原指向,那就完成不了了,所以在我们修改每一个节点的原指向的时候,需要对原指向进行存储,这样就能存有原指向的节点。 所以我们就定义一个正在修改指向的节点cur和一个cur的原指向节点curNext,那么就可以切断局部链表和后续链表的连接进行操作了,在每一个节点反转完成后再找到下一个节点进行操作。 此时cur正在第二个节点上,我们使用cur.next来存储cur的原指向,保证在cur节点反转后,后续链表不会失去联系。 且在第二个节点完成反转后,就使head指向cur所在节点,cur指向curNext所在节点,保证链表反转正常。 在每次反转开始的时候,都需要curNext = cur.next 来继续去存储正在进行反转的节点的原指向。 依然是按照上面的规则进行反转。 直到cur指向null的时候,反转结束,head最后走到了最后一个节点的位置,返回head节点即可。 除此之外,还需要判断如果没有节点的时候,要返回空;以及只有一个节点的时候,反转后还是一个节点。 代码实现 : public ListNode reverseList(ListNode head) { //讨论的是 没有节点 if (head == null){ return null; } //讨论的是 只有一个节点 if (head.next == null){ return head; } ListNode cur = head.next; head.next = null; while (cur != null){ ListNode curNext = cur.next; cur.next = head; head = cur; cur = curNext; } return head; } |
CopyRight 2018-2019 实验室设备网 版权所有 |